package LeetCode刷题.暑假刷的算法;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-08-15 09:11
 * @description: Functions of this class is 找出二叉树中第一个大于n的节点
 **/
public class 二叉树中第一个大于n的节点 {

    public static class TNode {
        int val;
        TNode left, right;
    }

    private static TNode createTree(int nums[],int start,int end) {
        TNode T=null;
        if(start<=end){
            int mid=(start+end+1)>>1;
            T=new TNode();
            T.val=nums[mid];
            T.left=createTree(nums,start,mid-1);
            T.right=createTree(nums,mid+1,end);
        }
        return T;
    }
    //找出最大的节点，一定在右边
    public static TNode getMaxNode(TNode T){
        if(T!=null){
            while (T.right!=null){
                T=T.right;
            }
        }
        return T;
    }

    //找出最小的节点，一定在左边
    public static TNode getMinNode(TNode T){
        if(T!=null){
            while (T.left!=null){
                T=T.left;
            }
        }
        return T;
    }

    private static TNode findMaxNum(TNode T){
        TNode ans=null;
        if(T!=null){
            TNode MaxNode=getMaxNode(T);
            TNode MinNode=getMinNode(T);
            int mid=(MaxNode.val+MinNode.val)>>1;

            while (T!=null){
                if(T.val<=mid){
                  T=T.right;
                }
                else {
                    ans=T;
                    T=T.left;

                }
            }
        }
        return ans;
    }
    public static void main(String args[]){
        int nums[]={1,2,3,4,5,6,7};
        TNode T=createTree(nums,0,nums.length-1);
        System.out.println("二叉树中第一个大于最中间节点的值为："+findMaxNum(T).val);
    }
}